Atari Mega Archive 2/Atari Mega Archive CD - Volume 2.iso/8bit/language/stacktst.txt

Internet Message Format | 1995-04-22 | 12KB

From hufnagel Thu Dec  1 09:16:15 1994
Return-Path: <hufnagel>
Received: by zippy.sonoma.EDU (4.1/SMI-4.0)
    id AA23081; Thu, 1 Dec 94 09:16:14 PST
Date: Thu, 1 Dec 94 09:16:14 PST
From: hufnagel (Michael Hufnagel)
Message-Id: <[e-mail]>
To: kendrick
Subject: here
Status: RO

>From [e-mail] Thu Dec  1 08:26:00 1994
To: [e-mail], [e-mail], [e-mail],
        [e-mail]
Subject: Recursion in Action!  This seems to do it!  (STACKTST.ACT/.C/.BAS)

The following file is the C code I first came up with when I was
thinking of how to go about adding a local-variable stack to Action!
so that PROCedures and FUNCtions can be made to do recursion.

I tested it out in Think C++ on a Macintosh but didn't trust it
since, well, C handles this by itself, so all I could be doing is
wasting memory!  But never fear, two files follow this:

-----------------begin-stacktst.c----------------------
/* StackTst.c: Stack Test program for adding recursion to Action! */

#include "stdio.h"

int sp;
int stack[1024];

void overflow()
{
    printf("Overflow\n");
}

void underflow()
{
    printf("Underflow\n");
}

void init()
{
    sp=0;
}

void push(int x)
{
    stack[sp]=x;
    sp=sp+1;
    if (sp>1024)
        overflow();
}

int pop()
{
    if (sp==0)
        underflow();
    else
    {
        sp=sp-1;
        return(stack[sp]);
    }
}

/* -- */

int factorial(int n)
{
    int m;

    if (n<=1)
        m=1;
    else
    {
        push(n);
        m=factorial(n-1);
        n=pop();
        m=m*n;
    }
    return m;
}

void main()
{
    prinf("6!=%d\n",factorial(6));
}

/* By Bill Kendrick 11/29/1994 */  /* See STACKTST.ACT... */

-----------end----------

Well, since I didn't trust it, I started writing another text program
in QBASIC on an IBM.  Of course, at first I started out writing the thing
with "SUBS" and "FUNCTIONS"!  Duh!  QBASIC probably uses a stack for
local variables too!  So I started over and just used GOSUBS and passed
variables to my GOSUB'd functions via "x" and "n" variables.  The code
looks much more drawn out than it needs to be in a higher level language,
but for you Atari BASIC and TurboBASIC XL users, you may find this useful
nonetheless.  BTW: This seems to work too! :)

----------begin-stacktst.bas-------
1 ' StackTst.Bas
2 ' by Bill Kendrick 11/29/1994
3 ' Test of StackTst.c code in (Q)BASIC without using real
4 ' FUNCs.

5 DIM stack(100)
6 GOTO 1000

10 ' push
11 stack(sp) = x
12 sp = sp + 1
13 RETURN

20 ' pop
21 sp = sp - 1
22 x = stack(sp)
23 RETURN

100 ' factorial
101 IF n <= 1 THEN
102   m = 1
103 ELSE
104   x = n      ' \ push(n)
105   GOSUB 10   ' /
106   n = n - 1      ' \
107   GOSUB 100      '  > m=factorial(n-1)
108   m = x          ' /
109   GOSUB 20   ' \ m=pop()
110   n = x      ' /
111   m = m * n
112 END IF
113 x = m        ' return(x)
114 RETURN

1000 ' main
1001 n = 6       ' \
1002 GOSUB 100   '  > print factorial(6)
1003 PRINT x     ' /
1004 END

----------end----------

Finally, after this last sucessful trial, I came up with the following
Action! code, based on the C code above.  I ran it, got "720" as a
result (6!=720), screamed and jumped up and down; proceeded to tell the
person on the other line what had just happened (giving her a breif
description of recursion and factorial), then apologized and asked her
to repeat what she was saying a moment before. <grin>  ANYWAYS, I hadn't
booted any DOS with the thing and was planning on using SIO2PC's Print-Thru
and Atari's built in P:rinter device to make a copy of the thing as a file
on my PC, but accidentally hit "D" for DOS instead of "E" for editor in
Action!'s monitor and poof it was gone and I was enjoying the OS's Self-Test
menu <sigh>.  The following is obviously not my ORIGINAL code <grin>,
AND IS NOT IDENTICAL to the C code!  This gives you a menu letting you
chose between FACTORIAL, FIBONACCI, and ACKERMANN recursive functions.
ACKERMANN has not been tested, and when doing FACTORIAL and FIBONACCI,
remember that I used INTs, so when it calculates values over 32767 or
below -32768, the variable will have over-/under-flowed and answers will
be wrong, but hell, at least it works for INTs! :)

----begin-stacktst.act-----
; STACKTST.ACT

; Local variable stack handler for
; Action! test program.

; By Bill Kendrick  11/29/1994

DEFINE STACKSIZE="200"
DEFINE LARGESTTYPE="CARD"             ; Type mismatches don't create errors,
                                      ; so use the largest (2-bytes) available

CARD SP                               ; Stack pointer
LARGESTTYPE ARRAY STACK(STACKSIZE)    ; Stack storage space

PROC OVERFLOW()
  PRINTE("OVERFLOW")                  ; Display error
  PRINT("STACK POINTER ABOVE ")
  PRINTCE(STACKSIZE)
  BREAK()                             ; and abort program
RETURN

PROC UNDERFLOW()
  PRINTE("UNDERFLOW")
  PRINTE("STACK POINTER BELOW 0")
  BREAK()
RETURN

PROC INIT()                           ; All we need to do here is reset the
  SP=0                                ; stack pointer either before a
RETURN                                ; recursive function's called or at
                                      ; program start.

PROC PUSH(LARGESTTYPE V)
  STACK(SP)=V                         ; Store value
  SP=SP+1                             ; Increment stack pointer
  IF SP>=STACKSIZE-2 THEN             ; Test for overflow
    OVERFLOW()
  FI
RETURN

LARGESTTYPE FUNC POP()
  LARGESTTYPE V

  IF SP=0 THEN                        ; Test for possible underflow
    UNDERFLOW()
  ELSE
    SP=SP-1                           ; Decrement stack pointer
    V=STACK(SP)                       ; Retrieve value
  FI
RETURN(V)

; ----------------------------------

INT FUNC FACTORIAL(INT N)
  INT M                               ; Temporary variable; its value is
                                      ; RETURN'd
  IF N<=1 THEN                        ; 1!=1..
    M=1
  ELSE
    PUSH(N)                           ; Push before recursion
    M=FACTORIAL(N-1)                  ; Call function for N-1, store in M
    N=POP()                           ; (Get old N after last recursion was
                                      ; returned from)
    M=M*N                             ; Multiply..
  FI
RETURN(M)                             ; ..and return value

INT FUNC ACKERMANN(INT X,Y)
  INT R

  R=0
  IF X=0 AND Y>=0 THEN
    R=Y+1
  ELSEIF Y=0 AND X>0 THEN
    PUSH(X)
    PUSH(Y)
    R=ACKERMANN(X-1,1)
    Y=POP()
    X=POP()
  ELSE
    PUSH(X)
    PUSH(Y)
    R=ACKERMANN(X,Y-1)
    Y=POP()
    X=POP()
    PUSH(X)
    PUSH(Y)
    R=ACKERMANN(X-1,R)
    Y=POP()
    X=POP()
  FI
RETURN(R)

INT FUNC FIBONACCI(INT N)
  INT R1,R2                           ; Temporary variable; its value is
                                      ; RETURN'd
  IF N=0 OR N=1 THEN                  ; FIB(0)=0,FIB(1)=1
    R1=N
    R2=0
  ELSE
    PUSH(N)                           ; Push before recursion
    R1=FIBONACCI(N-1)                 ; Call function for N-1, store in M
    N=POP()
    PUSH(R1)                          ; Push before recursion
    PUSH(N)                           ; Push before recursion
    R2=FIBONACCI(N-2)                 ; Call function for N-1, store in M
    N=POP()
    R1=POP()                          ; (Get old N after last recursion was
                                      ; returned from)
  FI
  R1=R1+R2
RETURN(R1)                            ; ..and return value

PROC MAIN()
  INT A,B,RESULT

  INIT()                              ; Init Stack
  PRINTE("1=FACTORIAL")
  PRINTE("2=ACKERMANN")
  PRINTE("3=FIBONACCI")
  A=INPUTB()
  IF A=1 THEN
    PRINTE("Factorial")                 ; Title/instructions:
    PUTE()                              ; (blank line (PUT End Of Line))
    PRINTE("Enter 'A' and I will")
    PRINTE("show you 'A!'.")
    PUTE()
    PRINTE("Enter '0' to quit.")
    DO
      PUTE()
      PRINT(" A=")                      ; Prompt (no EOL after)
      A=INPU